package Day23;
import java.util.*;

public class A3 {


    /**
     * 有0~n-1个城市，判断有多少个集群。相连的城市算一个集群
     * @param m
     * @return
     */
    public int citys (ArrayList<ArrayList<Integer>> m) {
        boolean[] visited = new boolean[m.size()];
        int ret=0;
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<m.size();i++) {
            if(!visited[i]) { //i城市没有被访问过
                queue.add(i);
                visited[i]=true;
                while (!queue.isEmpty()) {
                    ArrayList<Integer> t = m.get(queue.poll()); //取出一个城市的相连部分
                    for(int j=0;j<t.size();j++) { //取出所有相连的城市
                        if(i!=j) {
                            if(t.get(j)==1 && !visited[j]) { //说明i城市和这个城市相连
                                queue.add(j);
                                visited[j]=true;
                            }
                        }
                    }
                }
                ret++;
            }

        }
        return ret;
    }
}
